package Util;


public class List <A>
{
    private ListNode <A> first = null;
    private ListNode <A> last  = null;
    private int length = 0;

    public A getFirst()
    {
        return (this.first != null) ? this.first.getValue() : null;
    }

    public boolean isEmpty()
    {
    	return (this.first == null);
    }

    public int getLength()
    {
    	return this.length;
    }

    public A getNode(A value)
    {
    	ListNode<A> result = this.first;
    	
    	while (result != null)
    	{
    		if (result.value.equals(value))
    		{
    			return result.value;
    		}    
    		result = result.next;
    	}
    	
    	return null;
    }
    
    public A getNodeByIndex(int index)
    {
    	// if the list is empty
    	if (this.isEmpty())
    		return null;
    	
    	// index 0
    	ListNode<A> node = this.first;
    	
    	for (int i = 1; i <= index; i++)
    	{
    		node = node.next;
    		if (node == null)
    			return null;	// index out of boundaries
    	}
    	
    	return node.value;
    }
    
    public A removeNode(A value)
    {
    	ListNode<A> result = this.first;
    	do
    	{
    		if (result.value.equals(value))
    		{
    			if (result.previous != null)
    				result.previous.next = result.next;
    			else
    				this.first = result.next;
    			
    			if (result.next != null)
    				result.next.previous = result.previous;
    			else
    				this.last = result.previous;
    			
    			
    			this.length--;
    			    			
    			return result.value;    			
    		}    
    		result = result.next;
    	} while (result != null);
    	
    	return null;
    }
    
    public boolean updateNode (A value)
    {
    	if (this.getNode(value) == null)
    	{
    		return false;
    	}
    	else
    	{
    		ListNode<A> result = this.first;        	
        	while (result != null)
        	{
        		if (result.value.equals(value))
        		{
        			result.value = value;
        			return true;
        		}    
        		result = result.next;
        	}
        	
        	return false;		// this shouldn't happen, since we already checked the existence of the symbol
    	}
    }
    
    public boolean addNode (A value)
    {
    	if (this.getNode(value) != null)
    	{
    		return false;
    	}    	
    	
    	if (this.isEmpty())
    	{
    		this.first = new ListNode<A>(value);
    		this.last = this.first;
    	}
    	else
    	{
    		this.last = new ListNode<A>(value, this.last, null);
    		this.last.previous.next = this.last;
    	}
    	
    	this.length++;
    	
    	return true;
    }
    

    class ListNode <B>
    {
    	public ListNode<B> previous;
        public ListNode<B> next;
        public B value;

        public ListNode(B value)
        {
        	this(value, null, null);
        }

        public ListNode(B value, ListNode<B> previous, ListNode<B> next)
        {
        	this.previous = previous;
            this.next = next;
            this.value = value;
        }
        
        public ListNode<B> getNext()
        {
        	return this.next;
        }
        
        public B getValue()
        {
        	return this.value;
        }
    }
}